package arithmetic1.stack;
/*
    用栈解析中缀表达式
 */
public class Infix {
    /*
       用栈来解析中缀表达式过程:
           从左向右一次解析字符串，如果是数字，进入数栈，如果是符号，先判断符号栈里面有没有元素，
           如果符号栈中没有元素，则直接进符号栈。如果有符号，判断该符号与栈的符号那个优先级大，
           如果该符号优先级大于栈中符号的优先级，那么该符号进栈，否则从数栈中弹出两个数字，从
           符号栈中弹出一个符号，进行计算，将结果入数栈，将符号入符号栈，字符串解析完毕后从数栈里面
           弹出两个数，符号栈里弹出一个符号，进行计算，知道符号栈为空为止，数栈中留下的元素就是计算
           结果
       加入()之后的过程:
           在扫描到 ( 时进入括号模式，将后面的运算符优先级都加10，在扫描到 ) 时退出括号模式,后面符号优先级为正常优先级
           退出括号模式之后再遇到符号,先将括号模式里面的运算符都计算后再将该运算符进栈
           如果有多层小括号可以设置多级括号模式，每一级括号模式，运算符的优先级都额外加10
    */
    public static void main(String[] args) {
        String str="2-5-8*9+42";       // 13
        //创建数栈
        Stack numStack=new Stack(10);
        //创建符号栈
        Stack operStack=new Stack(10);
        //用来记录解析的位置
        int index=0;
        //用来拼接数字
        String num="";
        while (true){
            if (index>=str.length()){   //字符串已经解析完毕
                break;
            }
            //从str中取出一个字符来解析
            char ch=str.charAt(index);
            //判断该字符时运算符还是数字
            if(Stack.isOperation(ch)){    //是操作符
                if(operStack.isEmpty()){       //符号栈为空
                    //将符号进栈
                    operStack.push(ch);
                }else{      //符号栈不为空
                    if (Stack.priority(ch)<=Stack.priority((char)operStack.getTop())){  //该符号优先级小于等于栈中符号的优先级
                        //弹出符号栈的栈顶元素，弹出数栈栈顶的两个元素，进行计算
                        char oper=(char)operStack.pop();
                        int num1=numStack.pop();
                        int num2=numStack.pop();
                        int result=Stack.cul(num1,num2,oper);
                        //将计算结果入数栈
                        numStack.push(result);
                        //将符号进栈
                        operStack.push(ch);
                    }else { //该符号的优先级大于符号栈中元素的优先级
                        //将该符号进栈
                        operStack.push(ch);
                    }
                }
            }else{  //是数字
                //拼接多位数
                num+=ch;
                if(index==str.length()-1){   //当前已经扫描到字符串最后
                    //将num进数栈
                    numStack.push(Integer.parseInt(num));
                    //将num清空
                    num="";
                }else {     //当前没有扫描到字符串最后
                    if(Stack.isOperation(str.charAt(index+1))){ //数字的下一位是符号,直接把该数字进数栈
                        //将num进数栈,ASCII值比真实数字大48
                        numStack.push(Integer.parseInt(num));
                        //将num清空
                        num="";
                    }
                }
            }
            //将指针后移
            index++;
        }
        //字符串解析完毕后，一次从符号栈中去一个符号，从数栈中取两个数，来进行运算，将运算结果入数栈
        while (true){
            if (operStack.isEmpty()){       //符号栈为空
                break;
            }
            //从数栈中去两个数
            int num1=numStack.pop();
            int num2=numStack.pop();
            //从符号栈中取一个符号
            char oper=(char) operStack.pop();
            //计算
            int result=Stack.cul(num1,num2,oper);
            //将计算结果入数栈
            numStack.push(result);
        }
        //从数栈中取出计算结果
        int result=numStack.pop();
        System.out.println("计算结果为:"+result);
    }
}
